package com.hy;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 希尔排序
 * author: Mr.Du
 * Date: 2022/11/12
 * Time: 10:23
 */
public class ShellSort {
    
    public static void main(String[] args) {
        ShellSort sSort = new ShellSort();
        int[] nums = new int[10];
        Random r = new Random();
        // 跑五次
        for(int i = 0;i < 5;i++){
            for(int j = 0; j < nums.length;j++){
                nums[j] = r.nextInt(1000);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(nums));
            sSort.shellSort(nums);
            System.out.println("插入排序后的数组: ");
            System.out.println(Arrays.toString(nums));
        }
        
    }
    
    /**
     * 思想：和插入排序思想一致，只是有一个步长而已
     * @param nums
     */
    public void shellSort(int[] nums){
        int len = nums.length;
        int h = 1;
        // 计算最大步长
        while(h < len / 3){
            h = 3 * h + 1;
        }
        while(h > 0){
            for(int i = h;i < len;i += h){
                int tmp = nums[i];
                int j = i - h;
                while(j >= 0 && nums[j] > tmp){
                    nums[j+h] = nums[j];
                    j -= h;
                }
                nums[j + h] = tmp;
            }
            h = (h - 1) / 3;
        }
    }
}
